Conventional OFDM systems have not strongly required a high-speed operation in an IFFT/FFT block. However, recent wireless communication systems requires a ultrahigh data rate of several tens to hundreds Mbps and thus must use a parallel structure or other VLSI techniques. In general, an OFDM scheme requiring an IFFT/FFT block is widely used for high-rate data transmission. The IFFT/FFT block requires a large amount of multiplication and addition and thus these arithmetic operations must be processed very rapidly.
In the OFDM scheme, high-rate data are divided into a large number of data sequences and the data sequences are simultaneously transmitted using a plurality of subcarriers. The IFFT/FFT operation is an arithmetic operation of generating subcarriers and combining data into the subcarriers. In the OFDM system, a transmitter performs an IFFT operation for combining data into subcarriers and a receiver performs an FFT operation for obtaining the data from the subcarriers. An FFT arithmetic expression is obtained from a discrete Fourier transform (DFT) expression that can be given by Equation 1 below.
                              X          ⁡                      (            k            )                          =                              ∑                          n              =              0                                      N              -              1                                ⁢                                          ⁢                                    x              ⁡                              (                n                )                                      ⁢                          ⅇ                                                -                  j                                ⁢                                                      2                    ⁢                    π                                    N                                ⁢                kn                                                                        (        1        )                                                                                    X                ⁡                                  (                  0                  )                                            =                                                x                  ⁡                                      (                    0                    )                                                  +                                  x                  ⁡                                      (                    1                    )                                                  +                                  x                  ⁡                                      (                    2                    )                                                  +                                  x                  ⁡                                      (                    3                    )                                                                                                                                          X                ⁡                                  (                  1                  )                                            =                                                x                  ⁡                                      (                    0                    )                                                  +                                                      x                    ⁡                                          (                      1                      )                                                        ⁢                                      ⅇ                                                                  -                        j                                            ⁢                                                                        2                          ⁢                          π                                                4                                            ⁢                      1                                                                      +                                                      x                    ⁡                                          (                      2                      )                                                        ⁢                                      ⅇ                                          j                      ⁢                                                                        2                          ⁢                          π                                                4                                            ⁢                      2                                                                      +                                                      x                    ⁡                                          (                      3                      )                                                        ⁢                                      ⅇ                                                                  -                        j                                            ⁢                                                                        2                          ⁢                          π                                                4                                            ⁢                      3                                                                                                                                                              X                ⁡                                  (                  2                  )                                            =                                                x                  ⁡                                      (                    0                    )                                                  +                                                      x                    ⁡                                          (                      1                      )                                                        ⁢                                      ⅇ                                                                  -                        j                                            ⁢                                                                        2                          ⁢                          π                                                4                                            ⁢                      2                                                                      +                                                      x                    ⁡                                          (                      2                      )                                                        ⁢                                      ⅇ                                                                  -                        j                                            ⁢                                                                        2                          ⁢                          π                                                4                                            ⁢                      4                                                                      +                                                      x                    ⁡                                          (                      3                      )                                                        ⁢                                      ⅇ                                                                  -                        j                                            ⁢                                                                        2                          ⁢                          π                                                4                                            ⁢                      6                                                                                                                                                              X                ⁡                                  (                  3                  )                                            =                                                x                  ⁡                                      (                    0                    )                                                  +                                                      x                    ⁡                                          (                      1                      )                                                        ⁢                                      ⅇ                                                                  -                        j                                            ⁢                                                                        2                          ⁢                          π                                                4                                            ⁢                      3                                                                      +                                                      x                    ⁡                                          (                      2                      )                                                        ⁢                                      ⅇ                                                                  -                        j                                            ⁢                                                                        2                          ⁢                          π                                                4                                            ⁢                      6                                                                      +                                                      x                    ⁡                                          (                      3                      )                                                        ⁢                                      ⅇ                                                                  -                        j                                            ⁢                                                                        2                          ⁢                          π                                                4                                            ⁢                      9                                                                                                                              (        2        )            
In Equation 1, X(k) is the frequency-domain result from the FFT and x(n) is a time-domain input data value. In Equation 2,
  ⅇ            -      j        ⁢                  2        ⁢        π            N        ⁢    kn  is a coefficient multiplied by the input. Equation 2 expresses a 4-point DFT arithmetic operation and includes multiplications and additions. As can be seen from Equations 1 and 2, the amount of the arithmetic calculation increases as N increases.
The structure of the conventional IFFT/FFT block will now be described in detail.
FIG. 1 is a block diagram of an OFDM IFFT block including a QPSK modulator and an radix-24 DIF SDF 256-point IFFT block.
Referring to FIG. 1, the OFDM IFFT block includes a pre-processor 110, a QPSK modulator 130, an IFFT block 150, and a control block 170. The pre-processor performs convolution coding and interleaving. Binary data 120 of ‘1’ and ‘0’ are inputted into the QPSK modulator 130. The QPSK modulator 130 divides the inputted binary data 120 on a 2-bit basis, maps the divided data to a QPSK constellation diagram, and generates a complex output 140.
The IFFT block 150 uses an radix-24 DIF (decimation in frequency) SDF (single-path delay feedback) structure and is an 256-point IFFT block receiving 128-point complex data and 128-point ‘0’. The 256-point IFFT operation requires a 8-stage butterfly. However, since 128 points are constituted by ‘0’, a butterfly of one stage can be omitted. The radix-24 structure needs a multiplier only at three stages but does not need a multiplier at the remaining stages that requires multiplication by j. A multiplier 151 performs an arithmetic operation of j and does not actually perform multiplication. A butterfly1 152 as well as the other butterflies performs addition and subtraction on two inputted complex numbers. A multiplier2 153 actually performs multiplication by three coefficients, that is,
      (                  ⅇ                              -            j                    ⁢                                    2              ⁢              π                        256                    ⁢          32                    ,              ⅇ                              -            j                    ⁢                                    2              ⁢              π                        256                    ⁢          128                    ,              ⅇ                              -            j                    ⁢                                    2              ⁢              π                        256                    ⁢          160                      )    .These multiplication coefficients are controlled by the control block 170. By the above process, the IFFT block 150 outputs a complex result 160.
As above, the QPSK modulator obtains pre-processed binary data from complex data, and the IFFT block 150 performs addition and multiplication on the complex data to output time-domain complex data.
However, since the complex data from the QPSK modulator are transformed into time-domain complex data by the IFFT block including seven butterflies and seven multipliers, the arithmetic operation speed of the IFFT/FFT is proportional to the speed of the addition and multiplication. That is, the arithmetic operation speed of the IFFT/FFT is proportional to the number of the butterflies and the multipliers.